package everydayone.maxDistance;

import java.util.LinkedList;

/**
 * @Date 2020/03/29
 * @author 王光浩
 * @Thinking 使用层序遍历
 * @		 这题和感染橘子题目类似，我们将1作为感染源，每个1只能临近感染，被感染的病人在1天之后才具有传染性，最少多少天
 * @		所有的0将会被感染，我们先将所有的1入队，然后依次出队将每一个元素上下左右的所有0置为1，同时
 * @        将所有本轮置为1的元素入队，最后直到队列为空，记录轮数即可。
 * @Analysis 时间复杂度O（n*n），空间复杂度O（n），n——每行元素的个数。
 */
public class MyMethodOne {
	public int maxDistance(int[][] grid) {
		int count=0;
		LinkedList<Integer> indexX=new LinkedList<Integer>(); //保存当前层元素的x下标
		LinkedList<Integer> indexY=new LinkedList<Integer>(); //保存当前层元素的y下标
		for(int i=0;i<grid.length;i++) 
			for(int j=0;j<grid.length;j++)
				if(grid[i][j]==1) {
					indexX.add(i);
					indexY.add(j);
				}
		if(indexX.size()==0 || indexX.size()==grid.length*grid.length)return -1;
		//进行感染，将0逐层感染为1
		while(!indexX.isEmpty()) {
			int size=indexX.size();
			for(int i=0;i<size;i++) {
				int x=indexX.poll();
				int y=indexY.poll();
				helper(x,y,indexX,indexY,grid);
			}
			if(!indexX.isEmpty())count++;
		}
		return count;
    }
 	private void helper(int x,int y,LinkedList<Integer> indexX,LinkedList<Integer> indexY,int[][] grid) {
		int[] directionX= {0,0,1,-1};
		int[] directionY= {1,-1,0,0};
		for(int i=0;i<4;i++) {
			int currentX=x+directionX[i];
			int currentY=y+directionY[i];
			if(currentX>=0 && currentX<grid.length && currentY>=0 && currentY<grid.length && grid[currentX][currentY]==0 ) {
				grid[currentX][currentY]=1;
				indexX.add(currentX);
				indexY.add(currentY);
			}
		}
	}
}
